package com.xufx.algorithm.backtrace;

import java.util.ArrayList;
import java.util.List;

/**
 * leetcode 46. Permutations
 * @link https://leetcode.cn/problems/permutations/description/
 * describe: Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
 *
 * Example 1:
 *
 * Input: nums = [1,2,3]
 * Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * Example 2:
 *
 * Input: nums = [0,1]
 * Output: [[0,1],[1,0]]
 * Example 3:
 *
 * Input: nums = [1]
 * Output: [[1]]
 */
public class Leetcode46Permutations {

    public static List<List<Integer>> res = new ArrayList<>();
    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4};
        permute(nums);
        System.out.println(res);
    }
    // 定义方法。leetcode中的主方法
    public static void permute(int[] nums){
        List<Integer> trace = new ArrayList<>();
        backtrace(trace, nums);
    }
    // 回溯算法的核心框架
    // 两个参数分别是路径、选择列表
    public static void backtrace(List<Integer> trace, int[] nums){
        // 结束条件
        if(trace.size() == nums.length){
            // 满足结束条件，把路径放到最终结果中
            res.add(new ArrayList<>(trace));
            return;
        }

        for(int num:nums){
            // 正常情况下应该随递归的深入，选择列表nums越来越短，这里用contains判断，也是一样的
            if(trace.contains(num)){
                continue;
            }
            // 做选择
            trace.add(num);
            backtrace(trace, nums);
            // 撤销选择
            trace.remove(trace.size() - 1);
        }

    }
}
